#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <malloc.h>

#define N 1000

void merge_sort(int *a, int low, int high);
void merge(int * a, int low, int mid, int high);

int main(void)
{
	int i;
	int a[N];

	srand((int)time(NULL));

	for (i = 0; i < N; ++i)
	{
		a[i] = rand() % 10000;
	}

	merge_sort(a, 0, N);

	for (i = 0; i < N; ++i)
		printf("%d ", a[i]);
	printf("\n");

	return 0;
}

void merge_sort(int *a, int low, int high)
{
	int mid;
	if (high - low < 2) return; //递归基 该序列只有一个元素 是有序的
	mid = (low + high) / 2;

	merge_sort(a, low, mid);	//左半部分排序
	merge_sort(a, mid, high);	//右半部分排序

	merge(a, low, mid, high);	//合并俩个排好序的序列
}

void merge(int * a, int low, int mid, int high)
{
	int i, j, k;
	int * result = &a[low];	//result数组为最后结果
	int left_length = mid - low;
	int * left = (int *)malloc(sizeof(int) * left_length);
	int right_length = high - mid;
	int * right = &a[mid];

	for (i = 0; i < left_length; left[i] = result[i++]);//左半部分备份到left数组

	for (i = 0, j = 0, k = 0; j < left_length; )
	{
		if (k < right_length && right[k] < left[j]) result[i++] = right[k++];
		if (right_length <= k || left[j] <= right[k]) result[i++] = left[j++];
	}
	free(left);
}